package com.liunian.algorithmstudy.str;

public class ShortestPalindrome215 {

    public String shortestPalindrome1(String s) {
        char[] chars = s.toCharArray();
        char[] newChars = preprocess(chars);
        int n = newChars.length;
        int[] results = new int[n];
        int center = 0;
        int right = 0;
        int longgestLen = 0;
        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * center - i;
            if (i < right) {
                results[i] = Math.min(results[i_mirror], right - i);
            }
            while (newChars[i + 1 + results[i]] == newChars[i - 1 - results[i]]) {
                results[i]++;
            }
            if (results[i] + i > right) {
                right = i + results[i];
                center = i;
            }
            if (results[i] == i - 1) {
                longgestLen = results[i];
            }
        }
        String s1 = new String(chars, longgestLen, s.length() - longgestLen);
        StringBuffer sb = new StringBuffer(s1);
        return sb.reverse().append(s).toString();
    }

    private char[] preprocess(char[] chars) {
        char[] newChars = new char[2 * chars.length + 3];
        newChars[0] = '^';
        newChars[newChars.length - 1] = '$';
        newChars[newChars.length - 2] = '#';
        for (int i = 0; i < chars.length; i++) {
            newChars[2 * i + 1] = '#';
            newChars[2 * (i + 1)] = chars[i];
        }
        return newChars;
    }

    public static void main(String[] args) {
        ShortestPalindrome215 palindrome215 = new ShortestPalindrome215();
        System.out.println(palindrome215.shortestPalindrome("abcd"));
    }

    public String shortestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int n = s.length();
        int[] next = new int[n];
        int j = 0;
        for (int i = 1; i < n; i++) {
            while (j > 0 && chars[i] != chars[j]) {
                j = next[j - 1];
            }
            if (chars[i] == chars[j]) {
                j++;
            }
            next[i] = j;
        }
        int best = 0;
        for (int i = n - 1; i >= 0; i++) {
            while (best > 0 && chars[best] != chars[i]) {
                best = next[best - 1];
            }
            if (chars[i] == chars[best]) {
                best++;
            }
        }
        String s1 = new String(chars, best, n - best);
        StringBuilder sb = new StringBuilder(s1);
        return sb.reverse().append(s).toString();
    }

}
